A secret calculation method is a method of calculating a given function by a plurality of secret calculation devices performing calculation while communicating to/from one another. Moreover, the secret calculation method has such a characteristic that none of the secret calculation devices can acquire information on input/output to/from the function unless data to be handled are shared by a sufficient number of devices.
As a publicly known secret calculation method, a method disclosed in Non Patent Document 1 is known.
The method disclosed in Non Patent Document 1 involves distributing a secret S, which is a value in a certain field, to a plurality of devices by using a polynomial F satisfying F(0)=S in this field. It is assumed that when the number of devices is N and the number of secrets is less than K, the information on the input/output to/from the function cannot be acquired. It is also assumed that values of the field that differ depending on the device are assigned, and that the value of the field assigned to the ith device is denoted by X[i], where 1≤i≤N.
When a secret A is distributed to the plurality of devices, F[i]:=F(X[i]) of a randomly selected (K−1)th-order polynomial F satisfying F(0)=A is distributed to each ith device.
Similarly, for a secret B, G[i]:=G(X[i]) of a (K−1)th-order polynomial G satisfying G(0)=B is distributed to each ith device.
Regarding the secrets, the (K−1)th-order polynomials can be solved by a group of K or more devices. Thus, coefficients of F or G can be acquired, and F(0) or G(0) can consequently be calculated.
In order to calculate a value where A+B is distributed, each ith device calculates H[i]=F[i]+G[i]. This value is H(X[i]) acquired by assigning X[i] to the polynomial H having coefficients, each of which is a sum of corresponding coefficients of F and G, and is thus a value acquired by distributing A+B to the plurality of devices as in the cases of the secret A and the secret B.
As in the cases of the secret A and the secret B, the (K−1)th-order polynomial can be solved by a group of K or more devices. Thus, coefficients of H can be acquired, and H(0) can consequently be calculated.
When K*2≤N+1, in order to calculate a value where A*B is distributed, each ith device calculates H[i]=F[i]*G[i]. This value is H(X[i]) acquired by assigning X[i] to the 2Kth-order polynomial H(X)=F(X)*G(X), and is thus a value acquired by distributing A*B to the plurality of devices as in the cases of the secret A and the secret B. The order of H is 2K, which is different from the cases of the secret A and the secret B, and hence the 2Kth-order polynomial can be solved by a group of 2K or more devices. Thus, coefficients of H can be acquired, and H(0) can consequently be calculated.
The distribution method for A*B is different from that for the secret A and the secret B. In order to distribute A*B in the form of using the (K−1)th-order polynomial, each ith device generates a (K−1)th-order polynomial G from H[i], and distributes G(X[j]) to each jth device. With the method disclosed in Non Patent Document 1, all functions constructed by sums and products can be calculated in this way.
With the method disclosed in Non Patent Document 1, the addition and the multiplication in the field can easily be calculated, but 2K≤N+1 exists as a condition. When K is not equal to or more than 2, a single device can acquire a secret, and N is thus equal to or more than 3.
X[i] needs to be different for each different i, and hence, with the method disclosed in Non Patent Document 1, a Galois field GF(2) is not included in available fields. The Galois field GF(2) is not included, and hence the method disclosed in Non Patent Document 1 cannot use a sum as the exclusive OR.
As another publicly known secret calculation method, a method disclosed in Non Patent Document 2 is known.
Non Patent Document 2 includes a description relating to a method for a case where the number of devices is two. With this method, when two devices hold a bit, namely, an element b in the Galois field GF(2), in a distributed manner, b and c satisfying b+c=b mod 2 are distributed to and held by the respective devices.
With this method, when a certain bit A and a certain bit B are distributed to a device 1 and a device 2, the device 1 holds C and E and the device 2 holds D and F, where A=C+D mod 2 and B=E+F mod 2. On this occasion, an exclusive OR G of the bit A and the bit B is G=A+B mod 2, and the distributions thereof to the device 1 and the device 2 can be H=C+E mod 2 and J=D+F mod 2, respectively.
Each of the devices can calculate the distribution of the exclusive OR of the two distributed values through light calculation without communicating to/from the other device.
Similarly, when the bit A and the bit B are distributed and held, the following calculation is carried out so that the device 1 acquires L and the device 2 acquires M, where L and M are respective distributions of an AND K=A·B of those two bits, that is, satisfy L+M=K mod 2.
The device 1 randomly generates L. On this occasion, M=(C+D)·(E+F)=L mod 2, and the device 1 thus returns the following values to the device 2 without knowing the value of M in accordance with the values D and F held by the device 2. When (D,F)=(0,0), M=(C+0)·(E+0)+L mod 2 is returned. When (D,F)=(0,1), M=(C+0)·(1+E)+L mod 2 is returned. When (D,F)=(1,0), M=(1+C)·(E+0)+L mod 2 is returned. When (D,F)=(1,1), M=(1+C)·(1+E)+L mod 2 is returned.
The device 1 transmits to the device 2 the value dependent on the input to the device 2. The method in which the device 1 cannot know the input to the device 2 is implemented by a technology referred to as oblivious transfer between the device 1 and the device 2. However, this technology generally requires both devices to perform a large amount of calculation and communication.